For purposes of protecting sensitive data (data representing social security numbers, salaries, account information, and so forth) that is stored in a database from unauthorized access, the data may be encrypted. For example, the database may be a relational database that contains tables; and various aspects of the tables may be encrypted, such as schema keys and/or data fields of the tables. Encrypting the data in the database, however, may impose constraints on database-related functions. For example, it may be challenging due to the encryption to search the database for certain strings (a particular employee name, information pertaining to a particular department, and so forth).